- Теория Рамсея
-
Теория Рамсея, названная в честь Франка Рамсея — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. Задачи в теории Рамсея обычно звучат в форме вопроса «сколько элементов должно быть в некотором объекте, чтобы гарантированно выполнялось заданное условие или существовала заданная структура?».
Содержание
Важнейшие результаты
Предположим, например, что мы знаем, что n кроликов рассажены в m клеток. Насколько велико должно быть n, чтобы гарантированно в одной из клеток было как минимум 2 кролика? Согласно принципу Дирихле, если n > m, то найдется клетка, в которой будут минимум 2 кролика. Теория Рамсея обобщает этот принцип.
Теорема Рамсея
Сам Рамсей доказал следующую теорему:
Пусть даны числа . Тогда существует такое число R, что, как бы мы ни покрасили рёбра полного графа на R вершинах в n цветов, найдётся либо полный подграф 1-го цвета на вершинах, либо полный подграф 2-го цвета на вершинах, … либо полный подграф n-го цвета на вершинах.[1]
Она была также обобщена им на случай гиперграфа.Минимальное число , при котором для заданного набора аргументов существует указанная в теореме раскраска, называется числом Рамсея. Вопрос о значениях чисел Рамсея за небольшим исключением остается открытым.
Теорема Ван-дер-Вардена
Сходна по формулировке, но отличается доказательством теорема Ван-дер-Вардена (англ.):
Для всякого набора чисел существует такое число W, что, как бы мы не покрасили первые W натуральных чисел в n цветов, найдётся либо арифметическая прогрессия 1-го цвета длины , либо арифметическая прогрессия 2-го цвета длины , …, либо арифметическая прогрессия n-го цвета длины .[2]
Вместо множества натуральных чисел можно рассмотреть решётку , а арифметических прогрессий — фигуры в ней, гомотетичные данной, и утверждение теоремы останется верным (обобщённая теорема Ван-дер-Вардена).Теорема Хейлса-Джеветта
Для любых чисел и можно найти число такое, что если ячейки -мерного куба со стороной длины раскрашены в цветов, то существует хотя бы одна строка (столбец и т.п.) из одноцветных ячеек.[3]
Это значит, что при игре в многомерные крестики-нолики при любой длине строки и любом числе игроков можно найти такое число измерений, что ничья будет невозможна.
Особенности теории
Для результатов в рамках теории Рамсея характерны два свойства. Во-первых, они не конструктивны. Доказывается, что некоторая структура существует, но не предлагается никакого способа ее построения кроме прямого перебора. Во-вторых, чтобы искомые структуры существовали, требуется, чтобы объекты их содержащие, состояли из очень большого числа элементов. Зависимость числа элементов объекта от размера структуры как минимум экспоненциальная. Рональд Грэхем предложил приз US$1000 за доказательство того, что число Ван-дер-Вардена W(2,k)<2k2.[4] Обзор результатов до 1990 г. дан в работе[5]
Примечания
- ↑ Ramsey, F. P. (1930), "«On a problem of formal logic»", Proc. London Math. Soc. Series 2 Т. 30: 264–286, DOI 10.1112/plms/s2-30.1.264
- ↑ van der Waerden, B. L. (1927). «Beweis einer Baudetschen Vermutung». Nieuw. Arch. Wisk. 15: 212–216.
- ↑ Alfred Hales, Robert Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222–229.
- ↑ Graham, Ron (2007). «Some of My Favorite Problems in Ramsey Theory». INTEGERS (The Electronic Journal of Combinatorial Number Theory 7 (2): #A2.
- ↑ Graham, R.; Rothschild, B. & Spencer, J. H. (1990), «Ramsey Theory» (2nd ed.), New York: John Wiley and Sons, ISBN 0-471-50046-1.
Ссылки
Категории:- Комбинаторика
- Теория чисел
- Теория графов
- Теория множеств
Wikimedia Foundation. 2010.